package com.fps.webshop.question.interview.question;

import java.util.Arrays;

/**
 * 面试题 17.14. 最小K个数
 *
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 *
 * 示例：
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 *
 * 提示：
 *      0 <= len(arr) <= 100000
 *      0 <= k <= min(100000, len(arr))
 *
 *
 */
public class InterviewQuestion17_14 {

    /**
     * 第一版，最容易想到的方法，直接排序并输出，有些取巧了
     *
     * 提交结果	执行用时	内存消耗	语言	    提交时间	            备注
     * 通过      6 ms	48.1 MB	Java	2021/09/03 09:47
     *
     * 执行用时：6 ms, 在所有 Java 提交中击败了70.64%的用户
     * 内存消耗：48.1 MB, 在所有 Java 提交中击败了41.74%的用户
     */
    public static int[] smallestK(int[] arr, int k) {
        Arrays.sort(arr);
        return Arrays.copyOfRange(arr,0,k);
    }

    public static void main(String[] args) {
        int [] a = smallestK(new int[]{1,2,3,4,5,6,7},4);
        for(int aa : a){
            System.out.print(aa+" ");
        }
    }
}
